The Ziv-Lempel data compression algorithm, also sometimes referred to as the Ziv-Lempel-Welch (ZLW) algorithm, is commonly and widely used for the compression of data. ZLW is a loss-less compression algorithm meaning that it can be used with all types of data streams: the data after decompression, or expansion, is identical to the original data. Thus, this data compression method is not limited to a particular type of data; a particular type of application, such as video image compression; nor a particular type of data representation, i.e. a particular bit stream representation of real world data.
ZLW is believed to be patented by the Sperry Corporation. It is used by commercial programs and services. These include:
CompuServe--the GIF file format, PA1 Unix--the compress operation, PA1 PKWare Inc.--the PKZIP data compression program.
The only patent of SPERRY that has been found is U.S. Pat. No. 4,558,302 which does not mention Ziv and Lempel who have been credited with origination of the ZL development.
ZLW consists of two operations: a compression operation and an expansion operation. Both use data tables which arc built from the respective input data stream during the operation. The major component of both operations is the need to perform a match of the current input character or string against the entries already accumulated in the data table.
The computer system processing which results in a ZLW compressed file, or the inverse decompress operation, consumes significant computer resources. Such resource usage and the overhead time spent is justified by the savings in the amount of computer main storage and secondary storage, such as disk and tape, needed to retain the various data files.
Included is a necessary string entry table data pruning algorithm. The processing method of ZLW is to grow a dynamic data string table from the input data based on the contents and characteristics of the data. This table requires periodic pruning during the course of ZLW processing. ZLWCAM imposes similar requirements to prune the data string table.